Materi OSN-K

Tabel Kebenaran & Boolean

Konteks OSN: Kenapa Belajar Ini?

Di OSN, soal-soal logika percabangan bersarang yang rumit bisa disederhanakan dengan Aljabar Boolean. Pemahaman gerbang logika yang kuat akan membantumu menghindari kesalahan konyol saat melacak (tracing) alur program.

👩‍🏫 Secara Formal: Logika Boolean

Logika Boolean adalah sistem logika matematika yang hanya memiliki dua nilai kebenaran: True (1) dan False (0). Operator utama yang digunakan untuk menggabungkan nilai-nilai ini adalah AND (&&), OR (||), NOT (!), dan XOR (^).

Analogi Jaman Now

"Bayangin logika ini kayak syarat-syarat dalam kehidupan sehari-hari:"

  • AND (&&): Syarat masuk bioskop 'Bawa Tiket' AND 'Pakai Masker'. Kalau cuma bawa tiket tapi nggak pakai masker, ditolak. Harus DUA-DUANYA terpenuhi.
  • OR (||): Syarat masuk jalur khusus 'Punya Kartu VIP' OR 'Bawa Undangan'. Punya salah satu aja (atau dua-duanya) udah boleh masuk.
  • NOT (!): Ini kayak tombol 'Invert' (Kebalikan). Kamu bilang "Gak mungkin aku suka dia" ➔ !suka.
  • XOR (^): Syarat beli promo 'Pilih Es Teh' XOR 'Pilih Kopi'. Kamu cuma boleh pilih SALAH SATU. Kalau milih dua-duanya malah promonya batal karena maruk.

Mental Model: Filter Berlapis

Anggap operator logika sebagai saringan:

  • AND adalah Saringan Ketat: Sedikit saja ada kotoran (False), maka airnya dibuang (hasil False).
  • OR adalah Saringan Longgar: Asal ada satu saja emas (True), airnya diterima (hasil True).
A B A AND B (&&) A OR B (||) A XOR B (^)
False (0)False (0)False (0)False (0)False (0)
False (0)True (1)False (0)True (1)True (1)
True (1)False (0)False (0)True (1)True (1)
True (1)True (1)True (1)True (1)False (0)

Pola Pikir Salah yang Sering Terjadi (Common Wrong Thinking)

Miskonsepsi 1: "XOR (^) itu operasi pangkat, kayak di kalkulator HP."

Kenapa Salah? Dalam matematika biasa, 2^3 memang dibaca pangkat. Tapi di pemrograman (C++/Java), ^ murni untuk operator XOR bitwise. Kalau kamu mau pangkat, kamu HARUS pakai fungsi pow(2, 3).

Miskonsepsi 2: "Semua operator logika dijalankan dari kiri ke kanan sama rata."

Kenapa Salah? Mereka punya kasta (Prioritas/Precedence)! Kasta tertinggi: ! (NOT), kasta tengah: && (AND), kasta bawah: || (OR).
Contoh: True || False && False. Karena && lebih tinggi kastanya, dikerjain duluan. Jadinya: True || (False && False) ➔ True || False ➔ True.

Latihan Bertingkat (Logika Boolean)

Level 1: Pemanasan

bool A = true;
bool B = false;
bool C = (A || B) && !B;

Tampilkan Jawaban
1. (A || B) ➔ (True || False) ➔ True.
2. !B ➔ !False ➔ True.
3. Gabungkan: True && True ➔ True.
Akhir: C = true
Level 2: Tipe OSN (Jebakan Prioritas)

bool A = false;
bool B = true;
bool res = !A || A && B;

Tampilkan Jawaban
Jangan langsung baca dari kiri! Cari prioritas tertinggi dulu.
1. NOT (!) jalan duluan: !A = !false = true. Jadinya: true || false && true.
2. AND (&&) jalan kedua: false && true = false. Jadinya: true || false.
3. OR (||) jalan terakhir: true || false = true.
Akhir: res = true

Checkpoint: Uji Pemahamanmu

Coba tebak: Apa hasil dari operasi XOR berantai True ^ True ^ True? (Ingat, kerjakan dari kiri ke kanan)

Tampilkan Jawaban
Hasilnya True!
Langkah 1: True ^ True = False (Karena sama).
Langkah 2: False ^ True = True (Karena beda).

Rangkuman Kilat & Pattern OSN

Core Idea: "Operator logika adalah filter kebenaran berlapis dengan kasta (! lalu && lalu ||)."

  • AND (&&): Semua harus True baru mau True.
  • OR (||): Salah satu True, dia langsung ikut True.
  • XOR (^): Hanya True jika keduanya BEDA.
  • Urutan Dikerjakan: NOT (!) -> AND (&&) -> OR (||).

Pattern Recognition (Kapan memikirkan ini?)

Dalam menelusuri (tracing) kode di OSN, jangan evaluasi && jika kondisi pertamanya sudah False. Ini disebut Short-Circuit Evaluation. Ekspresi di sebelah kanannya 100% tidak akan dieksekusi, berapapun panjangnya!

Lab Interaktif: Evaluasi Boolean Cepat

Uji insting logikamu! Pilih nilai kebenaran dari ekspresi berikut (Asumsi: A = True, B = False, C = True)

Ekspresi Logika:

! (A && B) || (B ^ C)
Materi OSN-K

Operasi Bitwise

Konteks OSN: Kenapa Belajar Ini?

Banyak soal Olimpiade menggunakan bitwise untuk trik rahasia seperti: mengecek bilangan ganjil/genap super cepat (x & 1), membagi/mengali angka dengan 2 (x >> 1), atau menyimpan status/himpunan (Bitmasking). Ini materi wajib untuk optimasi algoritma agar terhindar dari *Time Limit Exceeded*.

👩‍🏫 Secara Formal: Konversi Desimal ke Biner

Sebelum masuk ke operasi Bitwise, kamu wajib paham cara mengubah bilangan desimal (basis 10) menjadi bilangan biner (basis 2). Komputer tidak paham angka 13 atau 100, ia hanya paham deretan 0 dan 1 (bit).

Analogi Jaman Now

"Bayangin angka biner itu deretan saklar lampu cerdas. Setiap saklar (dari kanan ke kiri) punya nilai dua kali lipat dari saklar sebelumnya: 1, 2, 4, 8, 16... Kalau kamu mau bikin angka 13, saklar mana aja yang harus di-ON-kan (diberi nilai 1)? Pastinya saklar bernilai 8, 4, dan 1. (8+4+1 = 13). Jadilah binernya 1101!"

Metode 1: Pembagian Berulang (Bagi 2)

Cara paling umum dan sering dipakai di soal OSN. Langkah-langkahnya:

  1. Bagi bilangan desimal dengan 2.
  2. Catat sisa pembagian (0 atau 1).
  3. Ambil hasil bagi (bulatkan ke bawah), lalu ulangi langkah 1.
  4. Lanjutkan sampai hasil baginya menjadi 0.
  5. Baca sisa dari BAWAH ke ATAS. Itulah hasil binernya!
Contoh: Konversi 13 ke Biner
13 / 2 = 6 sisa 1 ← bit paling kecil (LSB)
6 / 2 = 3 sisa 0
3 / 2 = 1 sisa 1
1 / 2 = 0 sisa 1 ← bit paling besar (MSB)
Baca dari bawah ke atas: 1310 = 11012

Metode 2: Tabel Posisi Bit (Pangkat 2)

Metode ini lebih cepat untuk angka kecil dan sering dipakai para peserta OSN sebagai "trik cepat".

Posisi Bit 27262524 23222120
Nilai Desimal 128643216 8421
13 = 0000 1101
10 = 0000 1010
6 = 0000 0110

Cara bacanya: "Apakah 13 mengandung 8? Ya (1). Sisa 13-8=5. Mengandung 4? Ya (1). Sisa 5-4=1. Mengandung 2? Tidak (0). Mengandung 1? Ya (1). Selesai! 13 = 1101"

Konversi Balik: Biner ke Desimal

Cukup jumlahkan nilai posisi yang bernilai 1.

Contoh: 11012 = ?
= (1 x 8) + (1 x 4) + (0 x 2) + (1 x 1)
= 8 + 4 + 0 + 1
= 13

Lab Interaktif: Konverter Biner

Coba masukkan angka desimal (0-255) dan perhatikan proses konversinya (pembagian berulang & tabel saklar bit)!

👩‍🏫 Secara Formal: Operator Bitwise

Operator Bitwise (&, |, ^, <<, >>) bekerja langsung pada representasi biner. Untuk mencari hasil 10 & 6, komputer akan mengubah 10 dan 6 ke biner, menyejajarkan posisinya, lalu melakukan operasi AND pada masing-masing kolom bit secara paralel.

Analogi Jaman Now

"Ibarat kamu ngerjain soal pilihan ganda 8 nomor (satu byte = 8 bit). Kamu (Angka 1) membandingkan LJK dengan temanmu (Angka 2).

Kalau pakai operator AND (&), soal itu dianggap BENAR (1) hanya jika jawabanmu BENAR dan jawaban temanmu BENAR. Kalau satu salah, nilainya 0. Kamu bandinginnya ya per nomor soal (per bit), atas bawah secara sejajar."

Mental Model: Scan Vertikal (Kolom demi Kolom)

Jangan pernah membayangkan bitwise dalam bentuk angka desimal (basis 10). Bayangkan angka tersebut tersusun menjadi blok Lego vertikal 0 dan 1.

  • Luruskan dari kanan ke kiri (dari bit terkecil).
  • Tembak logika (AND/OR/XOR) per kolom, jangan pedulikan kolom sebelahnya.

Visualisasi Penjajaran Bitwise

Trik Cepat OSN: Shift Left & Right

X << N (Shift Left): Menggeser bit ke kiri sebanyak N kali. Sama persis dengan mengalikan X dengan 2N.

X >> N (Shift Right): Menggeser bit ke kanan sebanyak N kali. Sama persis dengan membagi bulat X dengan 2N (sisa dibuang).

Pola Pikir Salah yang Sering Terjadi (Common Wrong Thinking)

Miskonsepsi 1: "Mengira >> 1 (Shift Right) selalu sama dengan pembagian normal."

Kenapa Salah? Shift Right (>> 1) melakukan pembagian bulat (integer division) yang membuang sisa desimalnya. Misalnya 5 >> 1 hasilnya 2 (bukan 2.5). Ini sangat berguna di Binary Search!

Miskonsepsi 2: "Saat menghitung 10 & 5, langsung mengira 10 & 5 = 0 karena angkanya beda jauh."

Kenapa Salah? Banyak yang lupa meratakan bit (padding). 10 itu 1010, 5 itu 101. Kolomnya harus sejajar persis dari KANAN! Anggap depannya ada nol: 1010 & 0101 = 0000.

Latihan Bertingkat (Operasi Bitwise)

Level 1: Konversi Cepat

Berapakah hasil dari 14 & 9?

Tampilkan Jawaban
14 = 1 1 1 0
09 = 1 0 0 1
------------ &
...= 1 0 0 0

1000 dalam desimal adalah 8.
Level 2: Trik Ganjil-Genap OSN

Jika kita punya angka sembarang X. Kenapa X & 1 == 1 pasti berarti X adalah bilangan ganjil?

Tampilkan Jawaban
Lihat biner dari angka 1: 00000001.
Semua bit di depannya adalah 0, kecuali bit paling ujung kanan (LSB).
Saat kita lakukan AND (&) terhadap X, semua bit depan X akan hancur jadi 0 (karena ketemu 0).
Hanya bit terakhir X yang tersisa. Kalau bit terakhirnya 1, berarti angka itu mengandung nilai 2^0 = 1, yang otomatis membuatnya ganjil.

Checkpoint: Uji Pemahamanmu

Coba pikirkan: Apa hasilnya jika sebuah angka di-XOR-kan dengan dirinya sendiri? Misalnya 10 ^ 10?

Tampilkan Jawaban
Hasilnya pasti 0!
Kenapa? Karena setiap bit dari angka tersebut akan bertemu dengan bit yang sama persis. Ingat aturan XOR: jika sama, hasilnya 0. Trik ini sering dipakai di soal untuk mencari elemen yang unik dalam array (elemen yang berpasangan akan saling meniadakan menjadi 0).

Rangkuman Kilat & Pattern OSN

Core Idea: "Bitwise mengoperasi angka dalam bentuk jejeran saklar (biner) dengan meratakannya dari kanan, bukan mengoperasikannya sebagai bilangan desimal."

  • Bitwise AND (&): Cocok untuk mencari irisan / mengekstrak nilai bit (Masking).
  • Bitwise OR (|): Cocok untuk menyalakan/menggabungkan bit.
  • Bitwise XOR (^): Bedanya apa? (Jika sama = 0, beda = 1). Bisa meniadakan angka yang sama.
  • Shift (<< dan >>): Jalan pintas untuk kali 2 atau bagi 2.

Pattern Recognition (Kapan memikirkan ini?)

Kalau di soal ada kalimat "operasi himpunan bagian (subset)", "status lampu", atau "mencari angka yang muncul ganjil kali", probabilitas besar penyelesaiannya menggunakan trik manipulasi Bitwise. Jangan pernah gunakan loop biasa karena akan terkena Time Limit Exceeded!

Materi OSN-K

Inferensi Logika Matematis

Konteks OSN: Kenapa Belajar Ini?

Soal OSN bagian Analitika (seperti soal Bebras/Panda) sering menyajikan cerita panjang dengan banyak aturan bersyarat. Tanpa teknik inferensi yang benar (Modus Ponens & Tollens), kamu akan kebingungan menarik kesimpulan mana yang valid dan mana yang hanya sekadar asumsi salah (Falasi).

👩‍🏫 Secara Formal: Modus Ponens & Tollens

Inferensi adalah proses menarik kesimpulan dari premis-premis yang ada. Terdapat dua pola dasar yang sah diakui dalam logika matematika: Modus Ponens (menegaskan) dan Modus Tollens (menyangkal).

Analogi Jaman Now

Modus Ponens: "Kalau main rank bareng joki (p), pasti menang (q). Nah, sekarang kamu lagi mabar sama joki (p). Kesimpulannya? Pasti menang (q)."

Modus Tollens: "Kalau HP di-charge (p), baterainya pasti nambah (q). Eh, pas kamu cek baterainya kok malah berkurang (bukan q). Kesimpulannya? Pasti HP-nya tadi belum dicolok ke listrik (bukan p)."

Mental Model: Aturan Satu Arah

Anggap panah → (Maka) sebagai jalan satu arah yang tidak bisa di-reverse sembarangan:

  • Kamu diizinkan maju searah panah (Modus Ponens).
  • Kamu diizinkan mundur HANYA JIKA kondisinya berlawanan/negatif dari tujuan (Modus Tollens).
  • Kamu TIDAK diizinkan mundur dengan kondisi positif. (Itu pelanggaran logika!)

Modus Ponens

Premis 1: p → q
Premis 2: p
Kesimpulan: q

P1: Jika hujan, maka jalanan basah.
P2: Sekarang hujan.
K: Jalanan basah.

Modus Tollens

Premis 1: p → q
Premis 2: ~q
Kesimpulan: ~p

P1: Jika hujan, maka jalanan basah.
P2: Jalanan tidak basah (~q).
K: Sekarang tidak hujan (~p).

Pola Pikir Salah yang Sering Terjadi (Falasi Logika)

Soal OSN sering sengaja menjebak dengan kesimpulan tidak valid. Waspadai dua jebakan ini:

Miskonsepsi 1 (Falasi Afirmasi Konsekuen): Diketahui "p → q" dan "q", langsung disimpulkan "p".

Kenapa Salah? Contoh: "Jika hujan (p), jalan basah (q)". Fakta di lapangan: "Jalan basah (q)". Kamu menyimpulkan "Pasti hujan (p)". SALAH! Jalan basah bisa jadi karena ada yang menyiram air, bukan cuma karena hujan.

Miskonsepsi 2 (Falasi Deniasi Anteseden): Diketahui "p → q" dan "~p", langsung disimpulkan "~q".

Kenapa Salah? Contoh: "Jika hujan (p), jalan basah (q)". Fakta di lapangan: "Tidak hujan (~p)". Kamu menyimpulkan "Jalan pasti tidak basah (~q)". SALAH! Sekali lagi, jalan bisa basah karena alasan lain.

Latihan Bertingkat (Inferensi Logika)

Level 1: Pemanasan

P1: Jika listrik padam, maka Wi-Fi mati.

P2: Wi-Fi masih menyala.

Tampilkan Kesimpulan
Ini menggunakan Modus Tollens.
Diketahui: p → q. Lalu diketahui ~q (Wi-Fi mati dinegasikan jadi menyala).
Maka kesimpulannya adalah ~p.
Kesimpulan: Listrik TIDAK padam.
Level 2: Tipe OSN (Berantai)

P1: Jika Andi rajin ngoding (p), maka Andi juara OSN (q).

P2: Jika Andi juara OSN (q), maka Andi dapat medali (r).

P3: Andi tidak dapat medali (~r).

Tampilkan Kesimpulan
Gunakan rantai Tollens (mundur perlahan):
1. Dari P2 (q → r) dan P3 (~r), kita simpulkan ~q (Andi tidak juara OSN).
2. Sekarang kita bawa ~q ke P1 (p → q). Karena ~q, maka simpulannya ~p.
Kesimpulan Akhir: Andi tidak rajin ngoding (~p).

Checkpoint: Uji Pemahamanmu

Coba pikirkan: Apa hasilnya jika diketahui premis: "Jika saklar dinyalakan, maka lampu menyala". Fakta: "Lampu menyala". Bisakah kita menyimpulkan "Saklar dinyalakan"?

Tampilkan Jawaban
TIDAK BISA! (Kesimpulan Tidak Sah)
Ini adalah jebakan Falasi Afirmasi Konsekuen. Lampu menyala bisa jadi karena alasan lain (misalnya ada generator cadangan atau disambar petir). Kita hanya bisa mundur (menyimpulkan p dari q) jika q dinegasikan (Modus Tollens: Lampu TIDAK menyala -> Saklar TIDAK dinyalakan).

Rangkuman Kilat & Pattern OSN

Core Idea: "Logika implikasi adalah panah satu arah; kamu bisa maju (Ponens) atau mundur hanya jika hasilnya negatif (Tollens)."

  • Modus Ponens: Maju searah (p → q, diketahui p, maka q).
  • Modus Tollens: Mundur karena negasi tujuan (p → q, diketahui ~q, maka ~p).
  • Jangan tertipu menarik kesimpulan dari akibat yang terjadi duluan. Itu Falasi!

Pattern Recognition (Kapan memikirkan ini?)

Pada soal bertipe cerita detektif atau analisis kasus Bebras, segera petakan setiap kalimat ke dalam bentuk simbol p → q. Jika soal menyajikan akibat yang salah (negasi), gunakan Modus Tollens berantai untuk membongkar teka-teki dari belakang ke depan.

Lab Interaktif: Detektif Logika

Perhatikan premis berikut:

P1: Jika server nge-lag (p), maka ping akan tinggi (q).

P2: Ping ternyata normal / tidak tinggi (~q).

Kesimpulan sah apa yang bisa kamu ambil?

Materi OSN-K

Lab OSN: Teka-Teki Logika Bebras

Uji semua pemahaman logikamu (Boolean & Inferensi) di studi kasus nyata soal Olimpiade Informatika Bagian A.

Mental Model: Trial & Error Terstruktur

Untuk teka-teki logika OSN yang memiliki aturan "Hanya satu yang jujur/bohong", jangan ditebak pakai feeling! Gunakan metode Asumsi-Kontradiksi:

1. Asumsikan Si A jujur.
2. Cek apakah asumsi ini membuat pernyataan lain bentrok aturan.
3. Kalau bentrok, berarti asumsimu salah. Lanjut tes Si B jujur.

Common Wrong Thinking

Miskonsepsi: Membaca semua label sekaligus dan pusing sendiri karena kelihatannya semuanya masuk akal atau semuanya bertentangan.

Koreksi: Berhenti membaca semua label secara acak. Fokus pada SATU SKENARIO dulu. Misal: "Oke, mari kita anggap kotak merah isinya medali. Apa yang terjadi pada label-labelnya?"

Kasus: Misteri 3 Kotak

Terdapat 3 kotak: Merah, Biru, dan Hijau. Salah satu kotak berisi medali emas. Masing-masing kotak memiliki label pernyataan. Aturan Main: Hanya ada TEPAT SATU label yang jujur (True), sisanya pasti bohong (False).

Kotak Merah

"Medali ada di sini"

Kotak Biru

"Medali tidak ada di sini"

Kotak Hijau

"Medali tidak ada di Kotak Merah"

Berdasarkan inferensi logikamu, di kotak manakah medali emas tersebut berada?

Question Card

Jika kamu melakukan operasi 5 & 3 (AND bitwise), berapakah hasilnya? Coba jelaskan langkah konversinya!

Checkpoint: Refleksi Analitika

Jika ada soal berbunyi: "A berkata B bohong, B berkata C bohong, C berkata A dan B bohong". Siapa yang harus kamu asumsikan jujur pertama kali?

Tampilkan Strategi
Mulai dari pernyataan yang memuat paling banyak variabel!
Dalam kasus ini, C membuat klaim ganda ("A dan B bohong"). Jika kita mengasumsikan C jujur, kita langsung mendapat status A dan B sekaligus (menghemat waktu). Selalu cari pernyataan paling informatif sebagai pijakan pertama asumsimu.

Rangkuman Kilat & Pattern OSN

Core Idea: "Dalam soal teka-teki logika OSN, tidak ada tebak-tebakan. Semuanya diselesaikan dengan membuktikan kontradiksi dari sebuah asumsi."

Pattern Recognition (Pola Bebras)

Jika soal mengatakan "Pemenangnya berbohong" atau "Hanya satu pernyataan yang benar", berhentilah mencari siapa yang benar secara langsung. Carilah dua pernyataan yang saling bertentangan (kontradiksi mutual). Jika A bilang "B bohong" dan B bilang "A jujur", mustahil keduanya benar. Salah satu pasti bohong. Ini mempersempit ruang pencarianmu secara drastis!

Modul Minggu 2 Selesai!
Kerjakan Kuis Logika Minggu 2